package com.example.demo.lc;

import java.util.Comparator;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
* @author wzh
* @date 2021/7/8 1:44 下午
* @Description
 * 给你一个整数 n ，请你找出并返回第 n 个 丑数 。
 *
 * 丑数 就是只包含质因数 2、3 和/或 5 的正整数。
 *
 *  
 *
 * 示例 1：
 *
 * 输入：n = 10
 * 输出：12
 * 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
 * 示例 2：
 *
 * 输入：n = 1
 * 输出：1
 * 解释：1 通常被视为丑数。
 *  
 *
 * 提示：
 *
 * 1 <= n <= 1690
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/ugly-number-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
public class LeetCode264 {

    public static void main(String[] args) {
        //System.out.println(nthUglyNumber(10));
//        PriorityQueue<Long> minHeap = new PriorityQueue<Long>((o1, o2) -> (int) (o2-o1));
//        minHeap.offer(3L);
//        minHeap.offer(5L);
//        minHeap.offer(7L);
//        System.out.println(minHeap.poll());
    }

    /**
    * @author wzh
    * @date 2021/7/8 6:30 下午
    * @Description  最小堆解决topK问题
    */
    public static int nthUglyNumber(int n) {
        int[] factors = {2, 3, 5};
        Set<Long> set = new HashSet<Long>();
        PriorityQueue<Long> minHeap = new PriorityQueue<Long>();
        set.add(1L);
        minHeap.offer(1L);
        int topK = 0;
        for (int i = 0; i < n; i++) {
            long curr = minHeap.poll();
            topK = (int) curr;
            for (int factor : factors) {
                long next = curr * factor;
                if (set.add(next)) {
                    minHeap.offer(next);
                }
            }
        }
        return topK;
    }

}
